package 二分查找;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 爱吃香蕉的可可.java
 * @Description TODO
 * @createTime 2020年11月21日 16:06:00
 * 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
 *
 *  
 *
 * 示例 1：
 *
 * 输入: piles = [3,6,7,11], H = 8
 * 输出: 4
 *
 *
 */
public class 爱吃香蕉的可可 {
    public class Solution {

        public int minEatingSpeed(int[] piles, int H) {
            int maxVal = 1;
            for (int pile : piles) {
                maxVal = Math.max(maxVal, pile);
            }

            // 速度最小的时候，耗时最长
            int left = 1;
            // 速度最大的时候，耗时最短
            int right = maxVal;

            while (left < right) {
                int mid = left + (right - left) / 2;

                if (calculateSum(piles, mid) > H) {
                    // 耗时太多，说明速度太慢了，下一轮搜索区间在
                    // [mid + 1, right]
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }

        /**
         * 如果返回的小时数严格大于 H，就不符合题意
         *
         * @param piles
         * @param speed
         * @return 需要的小时数
         */
        private int calculateSum(int[] piles, int speed) {
            int sum = 0;
            for (int pile : piles) {

                // 上取整可以这样写
                sum += (pile + speed - 1) / speed;

            }
            return sum;
        }
    }

}
